<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /* 思路：找出每个节点到叶子节点的所有路径。 */
            let tree = {
                val: 1,
                left: {
                    val: -2,
                    left: {
                        val: 1,
                        left: {
                            val: -1,
                        },
                    },
                    right: {
                        val: 3,
                    },
                },
                right: {
                    val: -3,
                    left: {
                        val: -2,
                    },
                },
            }
            var pathSum = function (root, targetSum) {
                let result = 0
                function preOrder(root) {
                    if (!root) return null
                    backTracking(root, [root.val], targetSum)
                    preOrder(root.left)
                    preOrder(root.right)
                }
                function backTracking(root, path, targetSum) {
                    if (!root) return null
                    //终止条件修改
                    let sum = path.reduce((pre, item) => (pre += item), 0)
                    if (targetSum == sum) {
                        //注意 不能直接return  因为可能会有
                        /*   1
                           -2
                          1
                         -1
                        的情况
                        */
                        result++
                    }

                    if (root.left) {
                        path.push(root.left.val)
                        backTracking(root.left, path, targetSum)
                        path.pop()
                    }
                    if (root.right) {
                        path.push(root.right.val)
                        backTracking(root.right, path, targetSum)
                        path.pop()
                    }
                }
                preOrder(root)
                return result
            }
            console.log(pathSum(tree, -1))
        </script>
    </body>
</html>
